/*
 * 高级算法模板库 - 大模拟和系统相关算法
 * 使用场景: 空间智能、并行分布式、可扩展计算、大数据智能相关问题
 * 包含: LRU缓存、一致性哈希、负载均衡、分布式算法、并行计算等
 */

#pragma once
#include "basic_template.hpp"
#include <chrono>

// LRU缓存 - 最近最少使用缓存
// 使用场景: 缓存管理、内存优化、页面置换
// 时间复杂度: O(1)的get和put操作
// 典型应用: 操作系统页面置换、数据库缓存、Web缓存
template <typename K, typename V>
class LRUCache
{
private:
    struct Node {
        K key;
        V value;
        Node *prev;
        Node *next;
        Node(K k, V v) : key(k), value(v), prev(nullptr), next(nullptr) {}
    };

    int capacity;
    unordered_map<K, Node *> cache;
    Node *head;
    Node *tail;

    void add_node(Node *node)
    {
        node->prev = head;
        node->next = head->next;
        head->next->prev = node;
        head->next = node;
    }

    void remove_node(Node *node)
    {
        node->prev->next = node->next;
        node->next->prev = node->prev;
    }

    void move_to_head(Node *node)
    {
        remove_node(node);
        add_node(node);
    }

    Node *pop_tail()
    {
        Node *last = tail->prev;
        remove_node(last);
        return last;
    }

public:
    // 构造函数：创建指定容量的LRU缓存
    // cap: 缓存的最大容量
    LRUCache(int cap) : capacity(cap)
    {
        head = new Node(K{}, V{});
        tail = new Node(K{}, V{});
        head->next = tail;
        tail->prev = head;
    }

    // 获取指定key的值，如果存在则将其移到最前面（最近使用）
    // key: 要查找的键
    // 返回值: 对应的值，如果不存在返回默认值
    V get(K key)
    {
        auto it = cache.find(key);
        if (it == cache.end()) {
            return V{}; // 返回默认值表示未找到
        }

        Node *node = it->second;
        move_to_head(node);
        return node->value;
    }

    // 插入或更新键值对，如果缓存已满则淘汰最久未使用的项
    // key: 要插入的键
    // value: 要插入的值
    void put(K key, V value)
    {
        auto it = cache.find(key);
        if (it != cache.end()) {
            Node *node = it->second;
            node->value = value;
            move_to_head(node);
        } else {
            Node *new_node = new Node(key, value);

            if (cache.size() >= capacity) {
                Node *tail_node = pop_tail();
                cache.erase(tail_node->key);
                delete tail_node;
            }

            cache[key] = new_node;
            add_node(new_node);
        }
    }

    // 检查指定key是否存在于缓存中
    // key: 要检查的键
    // 返回值: 存在返回true，否则返回false
    bool exists(K key)
    {
        return cache.find(key) != cache.end();
    }

    // 获取当前缓存中的元素数量
    // 返回值: 缓存中的元素个数
    int size() const
    {
        return cache.size();
    }
};

// 一致性哈希 - 分布式系统负载均衡
// 使用场景: 分布式缓存、负载均衡、数据分片
// 时间复杂度: O(log n)的查找操作
// 典型应用: Redis集群、CDN、分布式存储
class ConsistentHash
{
private:
    map<uint32_t, string> ring;
    int virtual_nodes;

    uint32_t hash_function(const string &key)
    {
        // 简单的哈希函数，实际使用可以用MD5或SHA1
        uint32_t hash = 0;
        for (char c : key) {
            hash = hash * 31 + c;
        }
        return hash;
    }

public:
    // 构造函数：创建一致性哈希环
    // vnodes: 每个物理节点对应的虚拟节点数量，用于提高负载均衡
    ConsistentHash(int vnodes = 150) : virtual_nodes(vnodes) {}

    // 向哈希环中添加一个节点
    // node: 节点标识符（如服务器名称或IP）
    void add_node(const string &node)
    {
        for (int i = 0; i < virtual_nodes; i++) {
            string vnode = node + "#" + to_string(i);
            uint32_t hash = hash_function(vnode);
            ring[hash] = node;
        }
    }

    // 从哈希环中移除一个节点
    // node: 要移除的节点标识符
    void remove_node(const string &node)
    {
        for (int i = 0; i < virtual_nodes; i++) {
            string vnode = node + "#" + to_string(i);
            uint32_t hash = hash_function(vnode);
            ring.erase(hash);
        }
    }

    // 根据key找到对应的节点（顺时针方向第一个节点）
    // key: 要查找的键
    // 返回值: 负责该key的节点标识符
    string get_node(const string &key)
    {
        if (ring.empty())
            return "";

        uint32_t hash = hash_function(key);
        auto it = ring.lower_bound(hash);

        if (it == ring.end()) {
            it = ring.begin();
        }

        return it->second;
    }

    // 获取多个节点用于数据复制
    // key: 要查找的键
    // count: 需要的节点数量
    // 返回值: 负责该key的多个节点列表
    vector<string> get_nodes(const string &key, int count)
    {
        vector<string> result;
        if (ring.empty())
            return result;

        uint32_t hash = hash_function(key);
        auto it = ring.lower_bound(hash);

        unordered_set<string> seen;
        for (int i = 0; i < count && seen.size() < ring.size() / virtual_nodes; i++) {
            if (it == ring.end()) {
                it = ring.begin();
            }

            if (seen.find(it->second) == seen.end()) {
                result.push_back(it->second);
                seen.insert(it->second);
            }
            ++it;
        }

        return result;
    }

    // 打印哈希环的状态（调试用）
    // 输出所有虚拟节点的哈希值和对应的物理节点
    void print_ring()
    {
        for (auto &p : ring) {
            cout << "Hash: " << p.first << " -> Node: " << p.second << endl;
        }
    }
};

// 布隆过滤器 - 空间高效的概率数据结构
// 使用场景: 大数据去重、缓存穿透防护、网络爬虫
// 时间复杂度: O(k)，k为哈希函数个数
// 典型应用: Redis布隆过滤器、爬虫URL去重、垃圾邮件过滤
class BloomFilter
{
private:
    vector<bool> bit_array;
    int size;
    int hash_count;

    vector<uint32_t> get_hashes(const string &item)
    {
        vector<uint32_t> hashes;
        uint32_t hash1 = 0, hash2 = 0;

        for (char c : item) {
            hash1 = hash1 * 31 + c;
            hash2 = hash2 * 37 + c;
        }

        for (int i = 0; i < hash_count; i++) {
            hashes.push_back((hash1 + i * hash2) % size);
        }

        return hashes;
    }

public:
    // 构造函数：创建布隆过滤器
    // expected_elements: 预期要插入的元素数量
    // false_positive_rate: 期望的误判率（默认1%）
    BloomFilter(int expected_elements, double false_positive_rate = 0.01)
    {
        size = -expected_elements * log(false_positive_rate) / (log(2) * log(2));
        hash_count = size * log(2) / expected_elements;
        bit_array.assign(size, false);
    }

    // 向布隆过滤器中添加元素
    // item: 要添加的元素
    void add(const string &item)
    {
        auto hashes = get_hashes(item);
        for (uint32_t hash : hashes) {
            bit_array[hash] = true;
        }
    }

    // 检查元素是否可能存在于集合中
    // item: 要检查的元素
    // 返回值: true表示可能存在，false表示一定不存在
    bool might_contain(const string &item)
    {
        auto hashes = get_hashes(item);
        for (uint32_t hash : hashes) {
            if (!bit_array[hash]) {
                return false;
            }
        }
        return true;
    }

    // 计算当前的误判率
    // 返回值: 当前的误判概率
    double get_false_positive_rate()
    {
        int set_bits = count(bit_array.begin(), bit_array.end(), true);
        double ratio = (double)set_bits / size;
        return pow(ratio, hash_count);
    }

    // 清空布隆过滤器
    void clear()
    {
        fill(bit_array.begin(), bit_array.end(), false);
    }
};

// 跳表 - 概率性数据结构
// 使用场景: 有序集合、范围查询、并发数据结构
// 时间复杂度: 平均O(log n)的查找、插入、删除
// 典型应用: Redis有序集合、LevelDB、并发编程
template <typename T>
class SkipList
{
private:
    struct Node {
        T value;
        vector<Node *> forward;
        Node(T val, int level) : value(val), forward(level + 1, nullptr) {}
    };

    Node *header;
    int max_level;
    int current_level;
    double probability;

    int random_level()
    {
        int level = 0;
        while ((double)rand() / RAND_MAX < probability && level < max_level) {
            level++;
        }
        return level;
    }

public:
    // 构造函数：创建跳表
    // max_lvl: 最大层数（默认16层）
    // p: 层数增长概率（默认0.5）
    SkipList(int max_lvl = 16, double p = 0.5)
        : max_level(max_lvl), current_level(0), probability(p)
    {
        header = new Node(T{}, max_level);
    }

    // 在跳表中查找指定值
    // target: 要查找的值
    // 返回值: 找到返回true，否则返回false
    bool search(T target)
    {
        Node *current = header;

        for (int i = current_level; i >= 0; i--) {
            while (current->forward[i] && current->forward[i]->value < target) {
                current = current->forward[i];
            }
        }

        current = current->forward[0];
        return current && current->value == target;
    }

    // 向跳表中插入一个值
    // value: 要插入的值
    void insert(T value)
    {
        vector<Node *> update(max_level + 1);
        Node *current = header;

        for (int i = current_level; i >= 0; i--) {
            while (current->forward[i] && current->forward[i]->value < value) {
                current = current->forward[i];
            }
            update[i] = current;
        }

        current = current->forward[0];

        if (!current || current->value != value) {
            int new_level = random_level();

            if (new_level > current_level) {
                for (int i = current_level + 1; i <= new_level; i++) {
                    update[i] = header;
                }
                current_level = new_level;
            }

            Node *new_node = new Node(value, new_level);

            for (int i = 0; i <= new_level; i++) {
                new_node->forward[i] = update[i]->forward[i];
                update[i]->forward[i] = new_node;
            }
        }
    }

    // 从跳表中删除指定值
    // value: 要删除的值
    // 返回值: 删除成功返回true，值不存在返回false
    bool remove(T value)
    {
        vector<Node *> update(max_level + 1);
        Node *current = header;

        for (int i = current_level; i >= 0; i--) {
            while (current->forward[i] && current->forward[i]->value < value) {
                current = current->forward[i];
            }
            update[i] = current;
        }

        current = current->forward[0];

        if (current && current->value == value) {
            for (int i = 0; i <= current_level; i++) {
                if (update[i]->forward[i] != current)
                    break;
                update[i]->forward[i] = current->forward[i];
            }

            delete current;

            while (current_level > 0 && !header->forward[current_level]) {
                current_level--;
            }

            return true;
        }

        return false;
    }

    // 范围查询：返回指定范围内的所有值
    // start: 范围起始值（包含）
    // end: 范围结束值（包含）
    // 返回值: 范围内所有值的有序列表
    vector<T> range_query(T start, T end)
    {
        vector<T> result;
        Node *current = header;

        for (int i = current_level; i >= 0; i--) {
            while (current->forward[i] && current->forward[i]->value < start) {
                current = current->forward[i];
            }
        }

        current = current->forward[0];

        while (current && current->value <= end) {
            if (current->value >= start) {
                result.push_back(current->value);
            }
            current = current->forward[0];
        }

        return result;
    }
};

// 分布式锁 - 基于时间戳的简单实现
// 使用场景: 分布式系统同步、资源互斥访问
// 时间复杂度: O(1)的加锁和解锁
// 典型应用: 分布式任务调度、资源分配、数据一致性
class DistributedLock
{
private:
    unordered_map<string, pair<string, ll>> locks; // resource -> (owner, timestamp)
    ll timeout_ms;

public:
    // 构造函数：创建分布式锁管理器
    // timeout: 锁的超时时间（毫秒），默认30秒
    DistributedLock(ll timeout = 30000) : timeout_ms(timeout) {}

    // 尝试获取指定资源的锁
    // resource: 资源标识符
    // owner: 锁的拥有者标识
    // 返回值: 获取成功返回true，资源已被锁定返回false
    bool acquire_lock(const string &resource, const string &owner)
    {
        ll current_time = chrono::duration_cast<chrono::milliseconds>(
                              chrono::system_clock::now().time_since_epoch())
                              .count();

        auto it = locks.find(resource);
        if (it != locks.end()) {
            // 检查锁是否过期
            if (current_time - it->second.second < timeout_ms) {
                return false; // 锁仍然有效
            }
        }

        locks[resource] = {owner, current_time};
        return true;
    }

    // 释放指定资源的锁
    // resource: 资源标识符
    // owner: 锁的拥有者标识（只有拥有者才能释放）
    // 返回值: 释放成功返回true，无权限或锁不存在返回false
    bool release_lock(const string &resource, const string &owner)
    {
        auto it = locks.find(resource);
        if (it != locks.end() && it->second.first == owner) {
            locks.erase(it);
            return true;
        }
        return false;
    }

    // 检查指定资源是否被锁定
    // resource: 资源标识符
    // 返回值: 被锁定返回true，未锁定或锁已过期返回false
    bool is_locked(const string &resource)
    {
        ll current_time = chrono::duration_cast<chrono::milliseconds>(
                              chrono::system_clock::now().time_since_epoch())
                              .count();

        auto it = locks.find(resource);
        if (it != locks.end()) {
            if (current_time - it->second.second < timeout_ms) {
                return true;
            } else {
                locks.erase(it); // 清理过期锁
            }
        }
        return false;
    }

    // 获取指定资源的锁拥有者
    // resource: 资源标识符
    // 返回值: 锁拥有者标识，如果未锁定返回空字符串
    string get_lock_owner(const string &resource)
    {
        auto it = locks.find(resource);
        if (it != locks.end()) {
            return it->second.first;
        }
        return "";
    }
};

// 负载均衡器 - 多种负载均衡算法
// 使用场景: 分布式系统、微服务架构、流量分发
// 时间复杂度: O(1)到O(n)，取决于算法
// 典型应用: API网关、反向代理、服务发现
class LoadBalancer
{
private:
    vector<string> servers;
    unordered_map<string, int> server_weights;
    unordered_map<string, int> server_connections;
    int round_robin_index;

public:
    // 构造函数：创建负载均衡器
    LoadBalancer() : round_robin_index(0) {}

    // 添加服务器到负载均衡池
    // server: 服务器标识符
    // weight: 服务器权重（用于加权算法），默认为1
    void add_server(const string &server, int weight = 1)
    {
        servers.push_back(server);
        server_weights[server] = weight;
        server_connections[server] = 0;
    }

    // 从负载均衡池中移除服务器
    // server: 要移除的服务器标识符
    void remove_server(const string &server)
    {
        servers.erase(remove(servers.begin(), servers.end(), server), servers.end());
        server_weights.erase(server);
        server_connections.erase(server);
    }

    // 轮询算法：依次选择服务器
    // 返回值: 选中的服务器标识符
    string round_robin()
    {
        if (servers.empty())
            return "";
        string server = servers[round_robin_index];
        round_robin_index = (round_robin_index + 1) % servers.size();
        return server;
    }

    // 加权轮询算法：根据权重概率选择服务器
    // 返回值: 选中的服务器标识符
    string weighted_round_robin()
    {
        if (servers.empty())
            return "";

        int total_weight = 0;
        for (const string &server : servers) {
            total_weight += server_weights[server];
        }

        int random_weight = rand() % total_weight;
        int current_weight = 0;

        for (const string &server : servers) {
            current_weight += server_weights[server];
            if (random_weight < current_weight) {
                return server;
            }
        }

        return servers[0];
    }

    // 最少连接算法：选择当前连接数最少的服务器
    // 返回值: 连接数最少的服务器标识符
    string least_connections()
    {
        if (servers.empty())
            return "";

        string best_server = servers[0];
        int min_connections = server_connections[best_server];

        for (const string &server : servers) {
            if (server_connections[server] < min_connections) {
                min_connections = server_connections[server];
                best_server = server;
            }
        }

        return best_server;
    }

    // 一致性哈希算法：根据key的哈希值选择服务器
    // key: 用于计算哈希的键
    // 返回值: 选中的服务器标识符
    string consistent_hash(const string &key)
    {
        if (servers.empty())
            return "";

        uint32_t hash = 0;
        for (char c : key) {
            hash = hash * 31 + c;
        }

        return servers[hash % servers.size()];
    }

    // 增加指定服务器的连接数（用于最少连接算法）
    // server: 服务器标识符
    void increment_connections(const string &server)
    {
        server_connections[server]++;
    }

    // 减少指定服务器的连接数（用于最少连接算法）
    // server: 服务器标识符
    void decrement_connections(const string &server)
    {
        if (server_connections[server] > 0) {
            server_connections[server]--;
        }
    }

    // 获取所有服务器列表
    // 返回值: 服务器标识符列表
    vector<string> get_servers() const
    {
        return servers;
    }

    // 获取指定服务器的当前连接数
    // server: 服务器标识符
    // 返回值: 当前连接数
    int get_connections(const string &server)
    {
        return server_connections[server];
    }
};

// 时间轮算法 - 高效的定时器实现
// 使用场景: 定时任务、超时处理、事件调度
// 时间复杂度: O(1)的插入和删除
// 典型应用: 网络超时、任务调度、缓存过期
template <typename T>
class TimingWheel
{
private:
    struct TimerNode {
        T data;
        ll expire_time;
        int slot;
        TimerNode(T d, ll t, int s) : data(d), expire_time(t), slot(s) {}
    };

    vector<vector<TimerNode *>> wheel;
    int wheel_size;
    int current_slot;
    ll tick_duration; // 每个槽位的时间长度（毫秒）
    ll start_time;

public:
    TimingWheel(int size = 3600, ll tick_ms = 1000)
        : wheel_size(size), current_slot(0), tick_duration(tick_ms)
    {
        wheel.resize(wheel_size);
        start_time = chrono::duration_cast<chrono::milliseconds>(
                         chrono::system_clock::now().time_since_epoch())
                         .count();
    }

    void add_timer(T data, ll delay_ms)
    {
        ll expire_time = start_time + delay_ms;
        int slot = (current_slot + delay_ms / tick_duration) % wheel_size;
        wheel[slot].push_back(new TimerNode(data, expire_time, slot));
    }

    vector<T> tick()
    {
        vector<T> expired;
        ll current_time = chrono::duration_cast<chrono::milliseconds>(
                              chrono::system_clock::now().time_since_epoch())
                              .count();

        auto &current_bucket = wheel[current_slot];
        auto it = current_bucket.begin();

        while (it != current_bucket.end()) {
            if ((*it)->expire_time <= current_time) {
                expired.push_back((*it)->data);
                delete *it;
                it = current_bucket.erase(it);
            } else {
                ++it;
            }
        }

        current_slot = (current_slot + 1) % wheel_size;
        return expired;
    }

    void advance_time(ll ms)
    {
        int slots_to_advance = ms / tick_duration;
        for (int i = 0; i < slots_to_advance; i++) {
            tick();
        }
    }
};

// 线程池 - 并行任务执行
// 使用场景: 并行计算、任务调度、CPU密集型操作
// 时间复杂度: O(1)的任务提交
// 典型应用: 并行算法、批处理、异步计算
template <typename T>
class ThreadPool
{
private:
    vector<function<T()>> task_queue;
    int max_tasks;
    int current_tasks;
    bool shutdown;

public:
    ThreadPool(int max_size = 100) : max_tasks(max_size), current_tasks(0), shutdown(false) {}

    bool submit_task(function<T()> task)
    {
        if (current_tasks >= max_tasks || shutdown) {
            return false;
        }

        task_queue.push_back(task);
        current_tasks++;
        return true;
    }

    vector<T> execute_all()
    {
        vector<T> results;

        for (auto &task : task_queue) {
            results.push_back(task());
        }

        task_queue.clear();
        current_tasks = 0;
        return results;
    }

    int get_queue_size() const
    {
        return current_tasks;
    }

    void clear()
    {
        task_queue.clear();
        current_tasks = 0;
    }

    void shutdown_pool()
    {
        shutdown = true;
    }
};

// MapReduce框架 - 分布式计算模型
// 使用场景: 大数据处理、分布式计算、数据分析
// 时间复杂度: O(n)的数据处理
// 典型应用: 日志分析、数据挖掘、机器学习
template <typename InputType, typename KeyType, typename ValueType>
class MapReduce
{
private:
    function<vector<pair<KeyType, ValueType>>(InputType)> mapper;
    function<ValueType(KeyType, vector<ValueType>)> reducer;

public:
    MapReduce(function<vector<pair<KeyType, ValueType>>(InputType)> map_func,
              function<ValueType(KeyType, vector<ValueType>)> reduce_func)
        : mapper(map_func), reducer(reduce_func) {}

    map<KeyType, ValueType> process(const vector<InputType> &input_data)
    {
        // Map阶段
        map<KeyType, vector<ValueType>> intermediate;

        for (const auto &input : input_data) {
            auto mapped = mapper(input);
            for (const auto &kv : mapped) {
                intermediate[kv.first].push_back(kv.second);
            }
        }

        // Reduce阶段
        map<KeyType, ValueType> result;
        for (const auto &kv : intermediate) {
            result[kv.first] = reducer(kv.first, kv.second);
        }

        return result;
    }

    // 并行处理版本（简化）
    map<KeyType, ValueType> parallel_process(const vector<InputType> &input_data, int num_threads = 4)
    {
        map<KeyType, vector<ValueType>> intermediate;

        // 简化的并行Map（实际实现需要真正的线程）
        int chunk_size = input_data.size() / num_threads;

        for (int t = 0; t < num_threads; t++) {
            int start = t * chunk_size;
            int end = (t == num_threads - 1) ? input_data.size() : (t + 1) * chunk_size;

            for (int i = start; i < end; i++) {
                auto mapped = mapper(input_data[i]);
                for (const auto &kv : mapped) {
                    intermediate[kv.first].push_back(kv.second);
                }
            }
        }

        // Reduce阶段
        map<KeyType, ValueType> result;
        for (const auto &kv : intermediate) {
            result[kv.first] = reducer(kv.first, kv.second);
        }

        return result;
    }
};

// 分布式哈希表 - 简化版本
// 使用场景: 分布式存储、缓存系统、数据分片
// 时间复杂度: O(1)的平均查找时间
// 典型应用: 分布式缓存、NoSQL数据库、CDN
template <typename K, typename V>
class DistributedHashTable
{
private:
    struct Node {
        string node_id;
        unordered_map<K, V> data;
        bool is_active;

        Node(string id) : node_id(id), is_active(true) {}
    };

    vector<Node> nodes;
    ConsistentHash hash_ring;
    int replication_factor;

public:
    DistributedHashTable(int replicas = 3) : replication_factor(replicas) {}

    void add_node(const string &node_id)
    {
        nodes.emplace_back(node_id);
        hash_ring.add_node(node_id);
    }

    void remove_node(const string &node_id)
    {
        hash_ring.remove_node(node_id);

        for (auto &node : nodes) {
            if (node.node_id == node_id) {
                node.is_active = false;

                // 数据迁移到其他节点
                for (const auto &kv : node.data) {
                    string key_str = to_string(hash<K>{}(kv.first));
                    auto target_nodes = hash_ring.get_nodes(key_str, replication_factor);

                    for (const string &target : target_nodes) {
                        if (target != node_id) {
                            put_to_node(target, kv.first, kv.second);
                            break;
                        }
                    }
                }

                node.data.clear();
                break;
            }
        }
    }

    void put(const K &key, const V &value)
    {
        string key_str = to_string(hash<K>{}(key));
        auto target_nodes = hash_ring.get_nodes(key_str, replication_factor);

        for (const string &node_id : target_nodes) {
            put_to_node(node_id, key, value);
        }
    }

    V get(const K &key)
    {
        string key_str = to_string(hash<K>{}(key));
        auto target_nodes = hash_ring.get_nodes(key_str, replication_factor);

        for (const string &node_id : target_nodes) {
            auto result = get_from_node(node_id, key);
            if (result.first) {
                return result.second;
            }
        }

        return V{}; // 未找到
    }

    bool remove(const K &key)
    {
        string key_str = to_string(hash<K>{}(key));
        auto target_nodes = hash_ring.get_nodes(key_str, replication_factor);

        bool removed = false;
        for (const string &node_id : target_nodes) {
            if (remove_from_node(node_id, key)) {
                removed = true;
            }
        }

        return removed;
    }

private:
    void put_to_node(const string &node_id, const K &key, const V &value)
    {
        for (auto &node : nodes) {
            if (node.node_id == node_id && node.is_active) {
                node.data[key] = value;
                break;
            }
        }
    }

    pair<bool, V> get_from_node(const string &node_id, const K &key)
    {
        for (const auto &node : nodes) {
            if (node.node_id == node_id && node.is_active) {
                auto it = node.data.find(key);
                if (it != node.data.end()) {
                    return {true, it->second};
                }
                break;
            }
        }
        return {false, V{}};
    }

    bool remove_from_node(const string &node_id, const K &key)
    {
        for (auto &node : nodes) {
            if (node.node_id == node_id && node.is_active) {
                return node.data.erase(key) > 0;
            }
        }
        return false;
    }
};

// 空间索引 - R树的简化实现
// 使用场景: 地理信息系统、空间查询、碰撞检测
// 时间复杂度: O(log n)的查询和插入
// 典型应用: GPS导航、游戏引擎、CAD系统
struct Rectangle {
    double x1, y1, x2, y2;

    Rectangle(double x1 = 0, double y1 = 0, double x2 = 0, double y2 = 0)
        : x1(x1), y1(y1), x2(x2), y2(y2) {}

    double area() const
    {
        return (x2 - x1) * (y2 - y1);
    }

    bool intersects(const Rectangle &other) const
    {
        return !(x2 < other.x1 || other.x2 < x1 || y2 < other.y1 || other.y2 < y1);
    }

    bool contains(const Rectangle &other) const
    {
        return x1 <= other.x1 && y1 <= other.y1 && x2 >= other.x2 && y2 >= other.y2;
    }

    Rectangle merge(const Rectangle &other) const
    {
        return Rectangle(min(x1, other.x1), min(y1, other.y1),
                         max(x2, other.x2), max(y2, other.y2));
    }
};

template <typename T>
class SpatialIndex
{
private:
    struct Node {
        Rectangle bounds;
        vector<pair<Rectangle, T>> entries;
        vector<Node *> children;
        bool is_leaf;

        Node(bool leaf = true) : is_leaf(leaf) {}
    };

    Node *root;
    int max_entries;

public:
    // 构造函数：创建空间索引
    // max_ent: 每个节点的最大条目数，默认为4
    SpatialIndex(int max_ent = 4) : max_entries(max_ent)
    {
        root = new Node(true);
    }

    // 向空间索引中插入一个矩形区域和关联数据
    // rect: 要插入的矩形区域
    // data: 与矩形关联的数据
    void insert(const Rectangle &rect, const T &data)
    {
        insert_recursive(root, rect, data);
    }

    // 查询与指定矩形相交的所有数据
    // rect: 查询矩形
    // 返回值: 所有相交区域的关联数据列表
    vector<T> query(const Rectangle &rect)
    {
        vector<T> result;
        query_recursive(root, rect, result);
        return result;
    }

    // 范围查询：查询指定坐标范围内的所有数据
    // x1, y1: 左下角坐标
    // x2, y2: 右上角坐标
    // 返回值: 范围内所有数据的列表
    vector<T> range_query(double x1, double y1, double x2, double y2)
    {
        return query(Rectangle(x1, y1, x2, y2));
    }

private:
    void insert_recursive(Node *node, const Rectangle &rect, const T &data)
    {
        if (node->is_leaf) {
            node->entries.push_back({rect, data});
            update_bounds(node);

            if (node->entries.size() > max_entries) {
                split_node(node);
            }
        } else {
            // 选择最佳子节点插入
            Node *best_child = choose_subtree(node, rect);
            insert_recursive(best_child, rect, data);
            update_bounds(node);
        }
    }

    void query_recursive(Node *node, const Rectangle &rect, vector<T> &result)
    {
        if (!node->bounds.intersects(rect)) {
            return;
        }

        if (node->is_leaf) {
            for (const auto &entry : node->entries) {
                if (entry.first.intersects(rect)) {
                    result.push_back(entry.second);
                }
            }
        } else {
            for (Node *child : node->children) {
                query_recursive(child, rect, result);
            }
        }
    }

    Node *choose_subtree(Node *node, const Rectangle &rect)
    {
        Node *best = node->children[0];
        double min_enlargement = calculate_enlargement(best->bounds, rect);

        for (int i = 1; i < node->children.size(); i++) {
            double enlargement = calculate_enlargement(node->children[i]->bounds, rect);
            if (enlargement < min_enlargement) {
                min_enlargement = enlargement;
                best = node->children[i];
            }
        }

        return best;
    }

    double calculate_enlargement(const Rectangle &bounds, const Rectangle &rect)
    {
        Rectangle merged = bounds.merge(rect);
        return merged.area() - bounds.area();
    }

    void update_bounds(Node *node)
    {
        if (node->is_leaf && !node->entries.empty()) {
            node->bounds = node->entries[0].first;
            for (int i = 1; i < node->entries.size(); i++) {
                node->bounds = node->bounds.merge(node->entries[i].first);
            }
        } else if (!node->children.empty()) {
            node->bounds = node->children[0]->bounds;
            for (int i = 1; i < node->children.size(); i++) {
                node->bounds = node->bounds.merge(node->children[i]->bounds);
            }
        }
    }

    void split_node(Node *node)
    {
        // 简化的分裂策略
        if (node->entries.size() <= max_entries)
            return;

        Node *new_node = new Node(true);
        int mid = node->entries.size() / 2;

        for (int i = mid; i < node->entries.size(); i++) {
            new_node->entries.push_back(node->entries[i]);
        }

        node->entries.resize(mid);
        update_bounds(node);
        update_bounds(new_node);

        // 如果这是根节点，创建新的根
        if (node == root) {
            Node *new_root = new Node(false);
            new_root->children.push_back(node);
            new_root->children.push_back(new_node);
            update_bounds(new_root);
            root = new_root;
        }
    }
};

// 大数据流处理 - 滑动窗口统计
// 使用场景: 实时数据分析、流式计算、监控系统
// 时间复杂度: O(1)的插入和查询
// 典型应用: 实时监控、异常检测、趋势分析
template <typename T>
class SlidingWindowStats
{
private:
    deque<pair<T, ll>> window;
    ll window_size_ms;
    T sum;
    T min_val, max_val;

public:
    // 构造函数：创建滑动窗口统计器
    // window_ms: 窗口大小（毫秒）
    SlidingWindowStats(ll window_ms) : window_size_ms(window_ms), sum(T{}) {}

    // 向窗口中添加新的数值
    // value: 要添加的数值
    void add_value(T value)
    {
        ll current_time = chrono::duration_cast<chrono::milliseconds>(
                              chrono::system_clock::now().time_since_epoch())
                              .count();

        // 移除过期数据
        while (!window.empty() && current_time - window.front().second > window_size_ms) {
            sum -= window.front().first;
            window.pop_front();
        }

        // 添加新数据
        window.push_back({value, current_time});
        sum += value;

        // 更新最值
        if (window.size() == 1) {
            min_val = max_val = value;
        } else {
            min_val = min(min_val, value);
            max_val = max(max_val, value);
        }
    }

    // 获取窗口内所有数值的总和
    T get_sum() const { return sum; }

    // 获取窗口内数值的平均值
    double get_average() const
    {
        return window.empty() ? 0.0 : (double)sum / window.size();
    }

    // 获取窗口内的最小值
    T get_min() const { return min_val; }

    // 获取窗口内的最大值
    T get_max() const { return max_val; }

    // 获取窗口内数值的数量
    int get_count() const { return window.size(); }

    // 获取最近的若干个数值
    // count: 要获取的数值个数
    // 返回值: 最近的数值列表（按时间顺序）
    vector<T> get_recent_values(int count) const
    {
        vector<T> result;
        int start = max(0, (int)window.size() - count);

        for (int i = start; i < window.size(); i++) {
            result.push_back(window[i].first);
        }

        return result;
    }
};

// 分布式共识算法 - Raft的简化版本
// 使用场景: 分布式系统一致性、集群管理、状态同步
// 时间复杂度: O(n)的消息传播
// 典型应用: 分布式数据库、配置管理、服务发现
class RaftConsensus
{
private:
    enum NodeState { FOLLOWER,
                     CANDIDATE,
                     LEADER };

    struct LogEntry {
        int term;
        string command;
        LogEntry(int t, string cmd) : term(t), command(cmd) {}
    };

    string node_id;
    NodeState state;
    int current_term;
    string voted_for;
    vector<LogEntry> log;
    int commit_index;
    vector<string> cluster_nodes;

public:
    // 构造函数：创建Raft节点
    // id: 节点标识符
    // nodes: 集群中所有节点的标识符列表
    RaftConsensus(string id, vector<string> nodes)
        : node_id(id), state(FOLLOWER), current_term(0), commit_index(-1), cluster_nodes(nodes) {}

    // 发起选举：尝试成为Leader
    // 返回值: 选举成功返回true，失败返回false
    bool start_election()
    {
        state = CANDIDATE;
        current_term++;
        voted_for = node_id;

        int votes = 1; // 自己的票
        int majority = cluster_nodes.size() / 2 + 1;

        // 简化：假设能获得足够票数
        if (votes >= majority) {
            state = LEADER;
            return true;
        }

        state = FOLLOWER;
        return false;
    }

    // 追加日志条目（仅Leader可以执行）
    // command: 要追加的命令
    // 返回值: 追加成功返回true，非Leader返回false
    bool append_entry(const string &command)
    {
        if (state != LEADER)
            return false;

        log.emplace_back(current_term, command);

        // 简化：假设大多数节点接受了日志
        commit_index = log.size() - 1;
        return true;
    }

    // 获取所有已提交的命令
    // 返回值: 已提交命令的列表
    vector<string> get_committed_commands()
    {
        vector<string> commands;
        for (int i = 0; i <= commit_index; i++) {
            commands.push_back(log[i].command);
        }
        return commands;
    }

    // 检查当前节点是否为Leader
    bool is_leader() const { return state == LEADER; }

    // 获取当前任期号
    int get_term() const { return current_term; }

    // 获取节点标识符
    string get_node_id() const { return node_id; }
};
